You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

給一個 array 不能取連續 index 的值，找到非連續 index 相加後最大的值。

Example

Input: nums = [1,2,3,1]
Output: 4
Explanation: 1(index-0) + 3(index-2) > 2(index-1) + 1(index-3)

Step

1. nums = [2] 則只有一個選項便是 2
   
2. nums = [2,7] 則有兩個選項，第一個是去第一間拿到 1 塊第二個是去第二間拿到 7 塊，去第二間拿到的錢幣較多所以放入 7，這時的 7 代表 nums = [1,7] 時可以拿到最多的錢
   
3. nums = [2,7,9] 有兩個選項
   • 拿 9 和 7 之前的房子中最多錢的，因為 7 連著 9 所以要跳過 7 找 7 之前的最大值
     
   • 不拿 9 而拿 9 之前的房子中最多錢的，而 9 之前最多錢的在 2 (nums = [2,7]) 已經算過並放進 dp 裡面了
     
     方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9] 時可以拿得最多錢
     
4. nums = [2,7,9,3] 有兩個選項

• 拿 3 和 9 之前的房子 [2,7] 中最多錢的，因為 9 連著 3 所以要跳過 9 找 9 之前的最大值，而 9 之前的最大值在 2 (nums = [2,7]) 已經算過並放進 dp 裡了
  
• 不拿 3 而拿 3 之前的房子 [2,7,9] 中最多錢的，而 3 之前最多錢的已經在 3 (nums = [2,7,9]) 中算過並放進 dp 中了
  
  方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9,3] 時可以拿得最多錢
  

5. nums = [2,7,9,3,1] 有兩個選項

• 拿 1 和 3 之前的房子 [2,7,9] 中最多錢的，因為 3 連著 1 所以要跳過 3 找 3 之前的最大值，而 3 之前的最大值在 3 (nums = [2,7,9]) 已經算過了並放進 dp 裡了
  
• 不拿 1 而拿 1 之前的房子 [2,7,9,3] 中最多錢的，而 1 之前最多錢的已經在 4 (nums = [2,7,9,3] 中算過並放入 dp 中了
  
  方法一和方法二的最大值放入 dp 中表示 nums = [2,7,9,3,1] 時可以拿得最多錢
  

Coding

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    if (nums.length === 2) return Math.max(nums[0], nums[1]);

    const dp = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for(let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }

    return dp[dp.length - 1];
};

Time complexity: O(n)